package main.com.cyz.Deque;

import main.com.cyz.Queue.Bean.TreeNode;

import java.util.*;

/**
 * @author fox
 * @version 1.0
 * @description
 * 力扣103
 * 给你二叉树的根节点 root ，返回其节点值的 锯齿形层序遍历 。（即先从左往右，再从右往左进行下一层遍历，以此类推，层与层之间交替进行）。
 *
 * 示例 1：
 *
 *
 * 输入：root = [3,9,20,null,null,15,7]
 * 输出：[[3],[20,9],[15,7]]
 * 示例 2：
 *
 * 输入：root = [1]
 * 输出：[[1]]
 * 示例 3：
 *
 * 输入：root = []
 * 输出：[]
 *
 *
 * 提示：
 *
 * 树中节点数目在范围 [0, 2000] 内
 * -100 <= Node.val <= 100
 * @date 2024/5/20 9:59
 */
public class LeetCode103 {

    public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
        List<List<Integer>> result = new ArrayList<>();
        if(root == null){
            return result;
        }
        Deque<TreeNode> deque = new ArrayDeque<>();
        deque.offer(root);
        int c1 = 1;
        boolean flag = true;
        while (!deque.isEmpty()){
            LinkedList<Integer> level = new LinkedList<>();
            int c2 = 0;
            for (int i = 0; i < c1; i++) {
                TreeNode treeNode = deque.poll();
                if (flag){
                    level.offerLast(treeNode.val);
                }else{
                    level.offerFirst(treeNode.val);
                }

                if (treeNode.left != null){
                    deque.offer(treeNode.left);
                    c2 ++;
                }
                if (treeNode.right != null){
                    deque.offer(treeNode.right);
                    c2 ++;
                }
            }
            flag = !flag;
            result.add(level);
            c1 = c2;
        }

        return result;

    }

}
